package class18;

/**
 * @author YZY
 * @since 2022/8/17 20:13
 * 假设有排成一行的N个位置记为1~N，N一定大于或等于2
 * 开始时机器人在其中的M位置上(M一定是1~N中的一个)
 * 如果机器人来到1位置，那么下一步只能往右来到2位置；
 * 如果机器人来到N位置，那么下一步只能往左来到N-1位置；
 * 如果机器人来到中间位置，那么下一步可以往左走或者往右走；
 * 规定机器人必须走K步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
 * 给定四个参数 N、M、K、P，返回方法数
 */
public class Code01_RobotWalk {

    // 暴力尝试
    public static int ways1(int N, int start, int aim, int K) {
        return process1(N, start, aim, K);
    }

    // 机器人当前来到的位置是cur，
    // 机器人还有rest步需要去走，
    // 最终的目标是aim，
    // 有哪些位置？1~N
    // 返回：机器人从cur出发，走过rest步之后，最终停在aim的方法数，是多少？
    public static int process1(int cur, int rest, int aim, int N) {
        if (rest == 0) { // 如果已经不需要走了，走完了！
            return cur == aim ? 1 : 0;
        }
        // (cur, rest)
        if (cur == 1) { // 1 -> 2
            return process1(2, rest - 1, aim, N);
        }
        // (cur, rest)
        if (cur == N) { // N-1 <- N
            return process1(N - 1, rest - 1, aim, N);
        }
        // (cur, rest)
        return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);
    }

    // 记忆化搜索
    public static int ways2(int N, int start, int aim, int K) {
        int[][] dp = new int[N + 1][K + 1];
        return process2(N, aim, dp, start, K);
    }

    private static int process2(int N, int aim, int[][] dp, int start, int K) {
        if (dp[start][K] != 0) {
            return dp[start][K];
        }
        int result;
        if (K == 0) {
            result = start == aim ? 1 : 0;
        } else if (start == 1) {
            result = process2(N, aim, dp, start + 1, K - 1);
        } else if (start == N) {
            result = process2(N, aim, dp, start - 1, K - 1);
        } else {
            result = process2(N, aim, dp, start - 1, K - 1) + process2(N, aim, dp, start + 1, K - 1);
        }
        return dp[start][K] = result;
    }

    // 动态规划
    public static int ways3(int N, int start, int aim, int K) {
        int[][] dp = new int[N + 1][K + 1];
        dp[aim][0] = 1;
        for (int reset = 1; reset <= K; ++reset) {
            dp[1][reset] = dp[2][reset - 1];
            for (int walk = 2; walk < N; ++walk) {
                dp[walk][reset] = dp[walk - 1][reset - 1] + dp[walk + 1][reset - 1];
            }
            dp[N][reset] = dp[N - 1][reset - 1];
        }
        return dp[start][K];
    }

    public static void main(String[] args) {
        System.out.println(ways1(5, 2, 4, 6));
        System.out.println(ways2(5, 2, 4, 6));
        System.out.println(ways3(5, 2, 4, 6));
    }
}
